package com.earthchen;

/**
 * 插入排序
 *
 * @author earthchen
 * @date 2018/8/10
 **/
public class InsertSort {


    /**
     * 直接插入排序（Straight Insertion Sorting）的基本思想：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，
     * 现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
     *
     * @param a
     */
    public static void sort(int[] a) {
        int len = a.length;
        int insertNum;
        //因为第一次不用，所以从1开始
        for (int i = 1; i < len; i++) {
            insertNum = a[i];
            // 序列元素个数
            int j = i - 1;
            //从后往前循环，将大于insertNum的数向后移动
            while (j >= 0 && a[j] > insertNum) {
                //元素向后移动
                a[j + 1] = a[j];
                j--;
            }
            //找到位置，插入当前元素
            a[j + 1] = insertNum;
        }
    }
}
